package liecai_class.day05;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 二叉树类
 */
public class BTree <T> {
    private BTNode<T> root;

    /**
     * 传入数组，数组内是按照树的前序遍历方式存放的二叉树的数据
     */
    public BTree(T [] arr) {
        //创建根
        this.root = createTree(arr,new int[]{0});
    }
    /**
     * 创建指定节点
     */
    private BTNode createTree(T [] arr,int [] index){
        //递归结束条件 - 如果遇到空节点，直接返回
        if(arr[index[0]] == null) return null;
        //创建当前节点
        BTNode nowNode = new BTNode(arr[index[0]]);
        //创建当前节点的左子节点，挂载好
        index[0] += 1;
        BTNode leftChild = createTree(arr,index);
        nowNode.setLeftChild(leftChild);
        //创建当前节点的右子节点，挂载好
        index[0] += 1;
        BTNode rightChild = createTree(arr,index);
        nowNode.setRightChild(rightChild);
        //返回创建好的节点
        return nowNode;
    }

    /**
     * 前序遍历 - 根左右
     */
    public void preOrder(){
        preOrder(root);
        System.out.println();
    }
    private void preOrder(BTNode node){
        //递归结束条件
        if(node == null)return;
        //打印根
        System.out.print(node.getData()+" ");
        //打印左
        preOrder(node.getLeftChild());
        //打印右
        preOrder(node.getRightChild());
    }

    /**
     * 中序遍历 - 左根右
     */
    public void inOrder(){
        inOrder(root);
        System.out.println();
    }
    private void inOrder(BTNode node){
        //递归结束条件
        if(node == null)return;
        //打印左
        inOrder(node.getLeftChild());
        //打印根
        System.out.print(node.getData()+" ");
        //打印右
        inOrder(node.getRightChild());
    }

    /**
     * 后序遍历 - 左右根
     */
    public void postOrder(){
        postOrder(root);
        System.out.println();
    }
    private void postOrder(BTNode node){
        //递归结束条件
        if(node == null)return;
        //打印左
        postOrder(node.getLeftChild());
        //打印右
        postOrder(node.getRightChild());
        //打印根
        System.out.print(node.getData()+" ");
    }

    /**
     * 层序遍历
     */
    public void levelOrder(){
        //定义一个队列
        Queue<BTNode> queue = new LinkedList<>();
        //根节点入队
        queue.offer(root);
        //循环遍历队列，取出队列中的元素
        BTNode ptr = null;
        while((ptr = queue.poll())!=null){
            //打印取出的元素
            System.out.print(ptr.getData()+" ");
            //如果有左子节点，左子节点入队
            if(ptr.getLeftChild()!=null){
                queue.offer(ptr.getLeftChild());
            }
            //如果有右子节点，右子节点入队
            if(ptr.getRightChild()!=null){
                queue.offer(ptr.getRightChild());
            }
        }
        System.out.println();
    }



    @Override
    public String toString() {
        return root.toString();
    }
}
